#include <iostream>
#define infinity 1e3
#define vertexNum 3
using namespace std;

void show(int **a){
    cout<<endl;
    for(int i=0; i < vertexNum; i++)
    {
        for(int j=0; j < vertexNum /*&& j > 0*/; j++){
            if( a[i][j]!= infinity && a[i][j] > 0 ) cout<<a[i][j]<<"    ";
            else cout<<"*    ";
        }
        cout<<endl;
    }
}

class graph{
public:
    int **adjGraph;
    int **previous;
    int **distance;

    graph();
    ~graph();
    void setedge(int st,int en ,int w);
    void floyd();

    int next_edge(int i, int j){
        for(int k=j+1;k<vertexNum;k++){
            if(adjGraph[i][k] != infinity)
                return k;
        }
        return -1;
    }
    int first_edge(int i){
        for(int j=0;j<vertexNum;j++)
        {
            if(adjGraph[i][j] != infinity)
                return j;
        }
        return -1;
    }
};

void graph::floyd(){
    for(int i = 0; i<vertexNum; i ++){
//        for(int j = first_edge(i); adjGraph[i][j] < infinity && j > 0; j = next_edge(i,j) ){
//            distance[i][j] = adjGraph[i][j];
//            cout<<distance[i][j]<<"\t";
//            previous[i][j] = i;
//        }
        for(int j = 0 ; j < vertexNum ; j++){
            distance[i][j] = adjGraph[i][j];
            if(adjGraph[i][j]<infinity)
                previous[i][j]=i;
        }
    }

    int tmp=infinity;
    for( int i = 0 ; i < vertexNum; i++ )
        for( int j = 0 ; j < vertexNum ; j ++)
            for( int k = 0; k < vertexNum ; k++){
                tmp = distance[i][k] + distance[k][j];
                if(distance[i][j] > tmp && j != i){
                    previous[i][j] = k;
                    distance[i][j] = tmp;
                    cout<<i<<":"<<endl;show(distance);
                }
            }
}

graph::graph(){
    adjGraph=(int**) new int*[6];
    previous=(int**) new int*[6];
    distance=(int**) new int*[6];
    for(int i = 0; i < vertexNum; i++ ){
        adjGraph[i] = new int[vertexNum];
        previous[i] = new int[vertexNum];
        distance[i] = new int[vertexNum];
    }

    for(int i = 0 ;i < vertexNum ; i++){
        for( int j = 0; j < vertexNum ; j++)
        {
            adjGraph[i][j] = infinity;
            previous[i][j] = -1;
            distance[i][j] = infinity ;
        }
    }
}
graph::~graph(){
    for(int i = 0 ; i < vertexNum ; i++){
        delete adjGraph[i];
        delete previous[i];
        delete distance[i];
    }
    delete adjGraph;
    delete previous;
    delete distance;
}
void graph::setedge(int st, int en, int w){
    adjGraph[st-1][en-1]=w;
}


int main()
{
    graph g;
    //page 174  4-20
    g.setedge(1,2,10);
    g.setedge(2,1,9);
    g.setedge(2,3,6);
    g.setedge(3,2,13);
    g.setedge(1,3,5);
    g.setedge(3,1,2);

    show(g.adjGraph);
    cout<<endl<<endl;

    g.floyd();
    cout<<endl<<"  finally:  ";
    show(g.distance);
    cout<<endl;
    show(g.previous);
}
